package com.example.tree.dp;

import com.example.tree.TreeNode;

/**
 * 给定一个二叉树的 root ，返回 最长的路径的长度 ，这个路径中的 每个节点具有相同值 。 这条路径可以经过也可以不经过根节点。
 *  两个节点之间的路径长度 由它们之间的边数表示。
 *
 *  示例 1:
 * 输入：root = [5,4,5,1,1,5]
 * 输出：2
 *
 *  示例 2:
 * 输入：root = [1,4,5,4,4,5]
 * 输出：2
 */
public class Leetcode687_LongestUnivaluePath {
    static class Solution {
        /**
         * 将任何路径（具有相同值的节点）看作是最多两个从其根延伸出的箭头
         * 具体地说，路径的根将是唯一节点，因此该节点的父节点不会出现在该路径中，而箭头将是根在该路径中只有一个子节点的路径
         * 那么该问题实际就是：对每个节点，求向左延伸的最长路径和向右延伸的最长路径之和(后序遍历)
         *     令 dfs(node) 表示为从节点 node 延伸出的最长箭头的长度。
         *         如果 node.Left 存在且与节点 node 具有相同的值，则该值就会是 1 + dfs(node.left)。
         *         在 node.right 存在的情况下也是一样。
         *     在计算箭头长度时，候选答案将是该节点在两个方向上的箭头之和。将这些候选答案记录下来，并更新最大值。
         * @param root
         * @return
         */
        public int longestUnivaluePath(TreeNode root) {
            class Stub {
                int res = 0;
                public int dfs(TreeNode root) {
                    if (root == null) return 0;
                    int leftRes = dfs(root.left);
                    int rightRes = dfs(root.right);
                    if (root.left != null && root.left.val == root.val)
                        leftRes += 1;
                    else leftRes = 0;
                    if (root.right != null && root.right.val == root.val)
                        rightRes += 1;
                    else rightRes = 0;

                    // 节点和左右子节点都相同，为左右之和
                    if (root.left != null && root.right != null && root.left.val == root.val && root.right.val == root.val)
                        res = Math.max(res, leftRes + rightRes);
                    else // 否则取较大的
                        res = Math.max(res, Math.max(leftRes, rightRes));
                    return Math.max(leftRes, rightRes);
                }
            }

            Stub stub = new Stub();
            stub.dfs(root);
            return stub.res;
        }
    }

    public static void main(String[] args) {
        // [1,null,1,1,1,1,1,1]
        //     1
        //             1
        //       1           1
        //   1       1    1
        TreeNode root = new TreeNode(1);
        root.left = null; root.right = new TreeNode(1);
        root.right.left = new TreeNode(1); root.right.right = new TreeNode(1);
        root.right.left.left = new TreeNode(1); root.right.left.right = new TreeNode(1);
        root.right.right.left = new TreeNode(1);
        System.out.println(new Solution().longestUnivaluePath(root));
    }
}
